<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
  <!-- 6. 将数组分成三个子数组的方案数
  我们称一个分割整数数组的方案是 好的 ，当它满足：
  数组被分成三个 非空 连续子数组，从左至右分别命名为 left ， mid ， right 。
  left 中元素和小于等于 mid 中元素和，mid 中元素和小于等于 right 中元素和。
  数组为非负数
  示例 1：
  输入：nums = [1,1,1]
  输出：1
  解释：唯一一种好的分割方案是将 nums 分成 [1] [1] [1] 。
 -->
</head>
<body>
  <script>
var waysToSplit = function(a) {
     let n = a.length;
        let v = new Array(n+1).fill(0);
        // 初始化前缀和数组
        for(let i = 1; i <= n; i++) {
            v[i] = v[i - 1] + a[i - 1];
        }
        // 返回值 ret
        let ret = 0;
        let M = 100000007;
        
        for(let i = 1; i < n; i++) {
            // 特判
            if(v[i] * 3 > v[n]) break;
            
            // 第一次二分找右边界
            let l = i + 1, r = n - 1;
            while(l <= r) {
                let mid = (l + r) >> 1;
                if(v[n] - v[mid] < v[mid] - v[i]) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            
            // 第二次二分找左边界
            let ll = i + 1, rr = n - 1;
            while(ll <= rr) {
                let mid = (ll + rr) >> 1;
                if(v[mid] - v[i] < v[i]) {
                    ll = mid + 1;
                } else {
                    rr = mid - 1;
                }
            }
            ret += (l - ll) % M;
        }
        return ret;
};
console.log(waysToSplit([1,1,1]));
  </script>
</body>
</html>